package org.algorithm.biubiu.wheel_1.数组.三月.第三周;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @date 2022-03-18 星期五17:33
 *
 * url:  https://leetcode-cn.com/problems/best-sightseeing-pair/
 *
 * 解题参考 {https://leetcode-cn.com/problems/best-sightseeing-pair/submissions/}
 */
public class 最佳观光组合 {

    public static void main(String[] args) {
        int[] nums = {8,1,5,2,6};
        System.out.println(maxScoreSightseeingPair(nums));
    }

    /**
     *
     * 输入：values = [8,1,5,2,6]
     * 输出：11
     * 解释：i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
     *
     */
    public static int maxScoreSightseeingPair(int[] values) {

        if(values==null||values.length==0){
            return -1;
        }
        int res = 0;
        int prvMax = values[0];
        for(int i=1;i<values.length;i++){
            res = Math.max(res,prvMax+values[i]-i);
            prvMax = Math.max(prvMax,values[i]+i);
        }
        return res;
    }

}
